import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;

/**
* @description: 785. 判断二分图
* @author hewei
* @date 2022/8/23 16:05
* @version 1.0
*/

public class IsBipartite {

    public static void main(String[] args) {
        IsBipartite isBipartite = new IsBipartite();
        int[][] nums = {{},{3},{},{1},{}};
        System.out.println(isBipartite.isBipartite(nums));
    }

    public boolean isBipartite1(int[][] graph) {
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> set2 = new HashSet<>();
        HashSet<Integer> set = new HashSet<>();
        for (int k = 0; k < graph.length; k++) {
            if (set.contains(k) || graph[k].length == 0) continue;
            Deque<Integer> queue = new LinkedList<>();
            queue.offer(k);
            set.add(k);
            set1.add(k);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Integer poll = queue.poll();
                    for (int j : graph[poll]) {
                        if (set1.contains(j)) return false;
                        if (set.contains(j)) continue;
                        set2.add(j);
                        set.add(j);
                        queue.offer(j);
                    }
                }
                HashSet<Integer> temp = set1;
                set1 = set2;
                set2 = temp;
            }
        }
        return true;
    }

    public boolean isBipartite(int[][] graph) {
        int[] color = new int[graph.length];
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < graph.length; i++) {
            if (color[i] != 0) continue;
            queue.add(i);
            color[i] = 1;
            while (!queue.isEmpty()) {
                Integer poll = queue.poll();
                for (int a : graph[poll]) {
                    if (color[a] == color[poll]) return false;
                    if (color[a] == 0) {
                        color[a] = -color[poll];
                        queue.offer(a);
                    }
                }
            }
        }
        return true;
    }
}
